OpenEd-Lab4
[ C:TaPiC ] Peer-to-peer process scheduling using eager queues This page was moved from NovellForge when it was shut down in 2009. Further work on eager queues has moved to the Eager Queue Protocol project on Launchpad. This work now forms part of a larger project GREAT Computing. See: http://greatc.wikia.com/wiki/Main_Page Aims and objectives This practical introduces the protocol UDP (user datagram protocol). As an example of UDP a scheduling mechanism is set up that combines take scheduling and FIFO (first in first out) scheduling across a network of processors. What's the point? There are many different trends in computing. For heterogeneous environments the trend has been to use ever more powerful processors based on the Von-Nuemann architecture. This trend is continuing and now virtual computers are running on top of a single processor architecture. As computer performance increases the abiliy to design and implement better software has not kept up. A major factor limiting ease of software development is versioning and software conflicts. This continues to be the case even with advances such as the .Net framework and the Java Virtual Machine. Eager take queueing For the first example we will assume: * That UDP is reliable * All processors receive each datagram correctly * Each worker process has the same capability * A maximum of L processors can be active at any one time. Assume we have a pool of processors, say L = N + 1 in all. Any processor can make a job request and broadcasts this request on the schedulilng channel. All of the other processors are idle and want to work. They all bid for the request and their bids conflict on the scheduling channel. How can it be organised so that this conflict is removed and work is picked up as quickly as possible? Let u be the unit of time. If it takes u units of time to broadcast a request and u units of time to respond to a request when there is no conflict, can we design a mechanism where the total time to allocate a job, where processors are available, is 2u? Eager Processes An eager process is made up of two main components, the Worker Process and the Scheduler Process. The scheduler process spends its life listening for and responding to job requests on the scheduling chanel. It tries to keep its worker process as busy as possible. The worker process gets jobs from the scheduler process and ... O------- | O----- Data Channels | | O--- | | | |-----------| | Worker | | Process | |-----------| | | |-----------| | Scheduler | | Process | |-----------| | O-- Scheduling Channel Last known transmission (LKT) vector The datagrams transmitted on the scheduling channel have the following structure: 0 7 8 15 16 23 24 31 +--------+--------+--------+--------+ | Source | Destination | | Port | Port | +--------+--------+--------+--------+ | | | | Length | Checksum | +--------+--------+--------+--------+ | Scheduling | | Code | +--------+--------+--------+--------+ / Last Known Transmission / / Vector / +--------+--------+--------+--------+ The LKT vector is transmitted in every scheduling datagram and a copy is also held on every scheduler processor. The structure of the LKT vector is made up of "last known transmission" - state pairs where the first item of the pair is the last known transmission from a processor measured in transmission counts and the second item of the pair is the state of the processor when it was last known to transmit. +------------------+-----------------+ Processor 1 | Last Known | Processor | | Transmission | State | +------------------+-----------------+ Processor 2 | Last Known | Processor | | Transmission | State | +------------------+-----------------+ Processor 3 | Last Known | Processor | | Transmission | State | +------------------+-----------------+ . . . +------------------+-----------------+ Processor L | Last Know | Processor | | Transmission | State | +------------------+-----------------+ An example At this point it is worth considering an example. Start with no proceesors available for scheduling. * The first processor to join the processing network listens to the scheduling channel. * On hearing no broadcasts for a given period, the processor takes address 1 and broadcasts its presence. +------------------+-----------------+ | UPDATE | +------------------+-----------------+ | 1 | WAITING | +------------------+-----------------+ | -1 | ADDRESS_FREE | +------------------+-----------------+ | -1 | ADDRESS_FREE | +------------------+-----------------+ | -1 | ADDRESS_FREE | +------------------+-----------------+ | -1 | ADDRESS_FREE | * The single processor continues to broadcast this datagram at regular intervals. At some later point anoth processor wants to join the network. * The second processor listens to the scheduling channel. * It picks up the datagram the first processor is transmitting. * It then brodacasts the following datagram: +------------------+-----------------+ | UPDATE | +------------------+-----------------+ | 2 | WAITING | +------------------+-----------------+ | 1 | WAITING | +------------------+-----------------+ | -1 | ADDRESS_FREE | +------------------+-----------------+ | -1 | ADDRESS_FREE | +------------------+-----------------+ | -1 | ADDRESS_FREE | While no job requests are being made each processor will keep updating the network state. After a given amount of time the processor at the head of the queue is expected to transmit an update. The processor at the head of the queue is the processor with the oldest last know transmission. In the example the next expected transmission will be: +------------------+-----------------+ | UPDATE | +------------------+-----------------+ | 1 | WAITING | +------------------+-----------------+ | 2 | WAITING | +------------------+-----------------+ | -1 | ADDRESS_FREE | +------------------+-----------------+ | -1 | ADDRESS_FREE | +------------------+-----------------+ | -1 | ADDRESS_FREE | More processors can continue to join the network and update their status in a similar way. In this way the LKT vector might end up as follows: +------------------+-----------------+ | UPDATE | +------------------+-----------------+ | 3 | WAITING | +------------------+-----------------+ | 2 | WAITING | +------------------+-----------------+ | 4 | WAITING | +------------------+-----------------+ | 5 | WAITING | +------------------+-----------------+ | 1 | WAITING | Processor 3 now broadcasts a job request: +------------------+-----------------+ | JOB REQUEST | +------------------+-----------------+ | 4 | WAITING | +------------------+-----------------+ | 3 | WAITING | +------------------+-----------------+ | 1 | BUSY | +------------------+-----------------+ | 6 | WAITING | +------------------+-----------------+ | 2 | WAITING | The oldest queued processor responds immediately: +------------------+-----------------+ | ACCEPT JOB | +------------------+-----------------+ | 5 | WAITING | +------------------+-----------------+ | 4 | WAITING | +------------------+-----------------+ | 2 | BUSY | +------------------+-----------------+ | 1 | BUSY | +------------------+-----------------+ | 3 | WAITING | Category:Education Category:OpenEd